/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-06-19
 * Time: 18:21
 */
public class Main {

    public int massage(int[] nums) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = nums.length;
        if(n == 0) {
            return 0;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        for(int i = 1; i < n; i++) {
            f[i] = nums[i] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) {
            return nums[0];
        }
        if(n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int yes = nums[0] + oneRob(nums, 2, n - 2);
        int no = oneRob(nums, 1, n - 1);
        return Math.max(yes, no);
    }
    public int oneRob(int[] nums, int left, int right) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for(int i = left + 1; i <= right; i++) {
            f[i] = nums[i] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[right], g[right]);
    }
    public int deleteAndEarn(int[] nums) {
        //1. 预处理
        //2. 创建dp表
        //3. 填表
        //4. 返回值
        int max = (int)1e4;
        int[] arr = new int[max + 1];
        for(int i = 0; i < nums.length; i++) {
            int index = nums[i];
            arr[index] += index;
        }
        int[] f = new int[max + 1];
        int[] g = new int[max + 1];
        for(int i = 1; i < max + 1; i++) {
            f[i] = arr[i] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[max], g[max]);
    }
    public int minCost(int[][] costs) {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = costs.length;
        int[][] dp = new int[n][3];
        for(int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }
        for(int i = 1; i < n; i++) {
            dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }

}
